package nine.test_9_14;

public class Solution {
    public int wiggleMaxLength(int[] nums) {
        // write code here
        if(nums == null || nums.length == 0) {
            return 0;
        }
        int i = 1;
        int len = 1;
        int n = nums.length;
        while (i < n && nums[i] == nums[i - 1]) {
            i++;
        }
        while (i < n) {
            if (nums[i] > nums[i - 1]) {
                len++;
            }
            while (i < n && nums[i] >= nums[i - 1]) {
                i++;
            }
            if (i < n) {
                len++;
            }
            while (i < n && nums[i] <= nums[i - 1]) {
                i++;
            }
        }
        return len;
    }
    public int minPathSum(int[][] grid) {
        // write code here
        int n = grid.length;
        int m = grid[0].length;
        int[][] dp = new int[n ][m ];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                if(i == grid.length - 1 && j == grid[i].length - 1) {
                    dp[i][j] = grid[i][j];
                } else if (i == grid.length - 1) {
                    dp[i][j] = grid[i][j] + dp[i][j + 1];
                } else if (j == grid[i].length - 1) {
                    dp[i][j] = grid[i][j] + dp[i + 1][j];
                } else {
                    dp[i][j] = grid[i][j] + Math.min(dp[i + 1][j],dp[i][j + 1]);
                }
            }
        }
        return dp[0][0];
    }
    boolean[] bs;
    int max = 0;
    public int pickGoods(int[] goods_list, int balance) {
        // write code here
        int n = goods_list.length;
        bs = new boolean[n];
        for (int i = 0; i < n; i++) {
            if(!bs[i]) {
                bs[i] = true;
                dfs(goods_list,balance,goods_list[i]);
                bs[i] = false;
            }
        }
        return max;
    }
    private void dfs(int[] goods_list, int balance,int k) {
        if(k > balance) {
            return;
        }
        max = Math.max(k,max);
        for (int i = 0; i < goods_list.length; i++) {
            if(!bs[i]) {
                bs[i] = true;
                dfs(goods_list,balance,goods_list[i]);
                bs[i] = false;
            }

        }
    }
}
